#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = true;
        for (int i = 1;i <= n;i++)
        {
            if (p[i - 1] == '*')
            {
                dp[0][i] = true;
            }
            else break;
        }
        s = " " + s;
        p = " " + p;
        for (int i = 1;i <= m;i++)
        {
            for (int j = 1;j <= n;j++)
            {
                if (p[j] >= 'a' && p[j] <= 'z')
                {
                    dp[i][j] = s[i] == p[j] ? dp[i - 1][j - 1] : false;
                }
                else if (p[j] == '?')
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else
                {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }
        // for(int i = 0;i <= m;i++)
        // {
        //     for(int j = 0;j <= n;j++)
        //     {
        //         cout<<dp[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        return dp[m][n];
    }
};